#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "set"

using namespace std;

/*HJJ QQ479287006
 *数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]
 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

static char getCharMe(int a) {
    if (a % 2 == 0)
        return '(';
    return ')';
}

static vector<string> ret;

static void back(int sizeD, string str, int left_size, int right_size) {



    //很明显一个规律 右面括号数量不能大于 左边且 都不能大于输入的值
    if (left_size > sizeD / 2 || right_size > sizeD / 2 || right_size > left_size)
        return;
    //出口 最后一个是) 且 深度为6
    //如何去重
    if (str.size() > 0 && str[str.size() - 1] == ')' && str.size() == sizeD && left_size == sizeD / 2 &&
        right_size == sizeD / 2) {
        if (ret.size() == 0)
            ret.push_back(str);
        else if (ret.size() >= 2) {
            if (ret[ret.size() - 1].compare(str) != 0 && ret[ret.size() - 2].compare(str) != 0)
                ret.push_back(str);
        } else if (ret[ret.size() - 1].compare(str) != 0) {
            ret.push_back(str);
        }

        return;
    }

    if (str.size() == sizeD)
        return;

    //第一个开始肯定是（
    // 1 2 3 4 5 6
    for (int i = 1; i < sizeD; ++i) {
        str.push_back(getCharMe(i));
        if (i % 2 == 0)left_size++;
        else right_size++;

        back(sizeD, str, left_size, right_size);

        if (str[str.size() - 1] == ')')
            right_size--;
        else
            left_size--;
        str.pop_back();


    }

}

vector<string> generateParenthesis(int n) {
    string s = "";
    int left_size = 1;
    int right_size = 0;
    s.push_back('(');
    back(n * 2, s, left_size, right_size);

    //定义并初始化一个vector

    set<string> s1(ret.begin(), ret.end());
    ret.assign(s1.begin(), s1.end());
//完成去重
    return ret;
    //传入 n*2
}

//虽然写出来了 但是仍然是超时间 没办法去重 网上答案如下

//vector<string> generateParenthesis(int n) {
//    vector<string> res;
//    func(res, "", 0, 0, n);
//    return res;
//}
//
//void func(vector<string> &res, string str, int l, int r, int n){
//    if(l > n || r > n || r > l) return ;
//    if(l == n && r == n) {res.push_back(str); return;}
//    func(res, str + '(', l+1, r, n);
//    func(res, str + ')', l, r+1, n);
//    return;
//}